/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-18
 * Time: 23:07
 */
public class Trie {
    //记录26个字符,用数组中某个位置是否为空来区分是否有这个字符
    public Trie[] currentChar;
    //用来标记这个字符是不是插入的某个字符串的结尾,以此来判断是否有某个字符串
    public boolean isEnd;
    public Trie() {
        this.currentChar=new Trie[26];
        this.isEnd=false;//这里初始化一定是false,否则相当于每个字符都作为了一个字符串的结尾
    }

    public void insert(String word) {
        Trie node=this;//this代表当前这个对象,因为每次调用函数肯定都是"根对象"
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            //还没有插入过这个字符
            if(node.currentChar[ch-'a']==null){
                //将该字符对应的位置创建一个trie就意味着对应的那个字符已经添加进去了
                node.currentChar[ch-'a']=new Trie();
            }
            //指针往下移动
            node=node.currentChar[ch-'a'];
        }
        //整个字符串添加完毕,结尾处设置为true
        node.isEnd=true;
    }

    public boolean search(String word) {
        Trie node=this;
        for(int i=0;i<word.length();i++){
            char ch=word.charAt(i);
            //如果没有匹配完说明没有找到对应的字符串
            if(node.currentChar[ch-'a']==null){
                return false;
            }
            //指针往下移动
            node=node.currentChar[ch-'a'];
        }
        //如果判断到最后不是字符串的结尾,则说明只是一个前缀,并没有对应的字符串
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie node=this;
        for(int i=0;i<prefix.length();i++){
            char ch=prefix.charAt(i);
            //如果没有匹配完说明没有以这个字符串开头的
            if(node.currentChar[ch-'a']==null){
                return false;
            }
            node=node.currentChar[ch-'a'];
        }
        return true;
    }
}